//
// Created by Jisam on 05/09/2024 9:27 PM.
// Solution of  P3956 [NOIP2017 普及组] 棋盘
// 2024-09-05 22:11:58  AC100 BFS +优先队列优化+ 快读
//#pragma GCC optimize(3)
#include <bits/stdc++.h>

using namespace std;
#define endl "\n"
#define PSI pair<string,int>
#define PII pair<int,int>
#define PDI pair<double,int>
#define PDD pair<double,double>
#define VVI vector<vector<int>>
#define VI vector<int>
#define VS vector<string>
#define PQLI priority_queue<int, vector<int>, less<int>>
#define PQGI priority_queue<int, vector<int>, greater<int>>
#define code_by_jisam ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
typedef long long i64;
typedef unsigned u32;
typedef unsigned long long u64;
typedef __int128 i128;

// 定义一个非常大的数作为无穷大的初始值
#define inf 0x3f3f3f3f

// 模板函数，用于读取输入的整数或浮点数
template <typename Tp>
void read(Tp &x){
    char c=getchar();x=0;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;
}

// 定义一个结构体，用于表示搜索过程中的每个节点状态
struct node{
    int x,y,c,w;
    // 重载运算符<，用于优先队列中节点的比较
    bool operator <(node b)const{
        return w>b.w;
    }
};

// 定义一个优先队列，用于BFS搜索过程中节点的存储
priority_queue<node>q;

// 定义数组，用于表示在棋盘上移动的方向和对应的魔法代价
int dx[]={0,1,0,-1,1,1,-1,-1,0,2,0,-2};
int dy[]={1,0,-1,0,1,-1,1,-1,2,0,-2,0};
int dw[]={0,0,0,0,2,2,2,2,2,2,2,2};

// 定义二维数组，用于存储棋盘上每个格子的颜色和BFS过程中的最短路径
int a[105][105],dis[105][105];

// 定义变量n和m，分别表示棋盘的行数和列数
int n,m;

// 实现BFS搜索算法，用于计算从(1,1)到(m,n)的最短路径
void bfs(){
    // 初始化dis数组，表示从起点到每个格子的最短路径
    memset(dis,0x3f,sizeof(dis));
    dis[1][1]=0;

    // 将起点加入优先队列，开始搜索
    q.push((node){1,1,a[1][1],dis[1][1]});
    node cur,nxt;

    // 循环搜索，直到队列为空
    while(!q.empty()){
        cur=q.top();q.pop();
        if(dis[cur.x][cur.y]<cur.w)continue;

        // 遍历所有可能的移动方向
        for(int i=0;i<12;i++){
            nxt.x=cur.x+dx[i];
            nxt.y=cur.y+dy[i];
            nxt.w=cur.w+dw[i];

            // 检查新位置是否在棋盘内
            if(nxt.x<=0||nxt.x>m||nxt.y<=0||nxt.y>m)continue;

            // 获取新位置的颜色
            nxt.c=a[nxt.x][nxt.y];
            if(!nxt.c)continue;//检查 nxt.c 是否为0（表示该位置没有颜色)，则跳过当前循环迭代

            // 根据颜色是否相同，更新路径代价
            if(cur.c!=nxt.c)nxt.w++;

            // 如果找到更短的路径，更新dis数组，并将新节点加入队列
            if(dis[nxt.x][nxt.y]>nxt.w){
                dis[nxt.x][nxt.y]=nxt.w;
                q.push(nxt);
            }
        }
    }
}

// 主要的解题函数，用于读取输入、调用BFS搜索并输出结果
void solution() {
    // 读取输入数据
    int x,y,c;
    read(m);read(n);

    // 初始化棋盘
    for(int i=1;i<=n;i++){
        read(x);read(y);read(c);
        a[x][y]=c+1;
    }

    // 进行BFS搜索
    bfs();

    // 处理特殊情况：如果目标位置(m,m)无色
    if(!a[m][m]){
        int ans=min(dis[m][m-1],dis[m-1][m])+2;
        if(ans>=inf)puts("-1");
        else printf("%d\n",ans);
    }
    else{
        // 如果目标位置有颜色，输出最短路径
        if(dis[m][m]==inf)puts("-1");
        else printf("%d\n",dis[m][m]);
    }
}


int main() {
//    code_by_jisam;
    int T = 1;
//    cin >> T;
    while (T--) {
        solution();
    }
    return 0;
}